Car had 140k miles and they were stuck pretty good. I soaked 'em down with PB Blaster and they came right out. I was amazed. Are you using anything like that?
By the way, I used a crows foot on a swivel joint and two 10 inch extensions to get the driver's side O2 sensor out. Worked for me...but then agin I didn't have the turbos to deal with.